class Solution
{
public:
    int collectTheCoins(vector<int> &coins, vector<vector<int>> &edges)
    {
        int n = coins.size();
        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        vector<int> removed(n, 0);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            degree[edge[1]]++;
            degree[edge[0]]++;
        }

        queue<int> q;

        // 递归去除 coin 为 0 的叶子节点
        for (int i = 0; i < n; i++)
        {
            if (coins[i] == 0 && degree[i] == 1)
            {
                q.push(i);
                removed[i] = 1;
            }
        }

        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            for (auto neighbor : graph[node])
            {
                if (removed[neighbor])
                {
                    continue;
                }
                degree[neighbor]--;
                if (degree[neighbor] == 1 && coins[neighbor] == 0)
                {
                    q.push(neighbor);
                    removed[neighbor] = 1;
                }
            }
        }

        // 再去除图的最外两层
        for (int i = 0; i < n; i++)
        {
            if (removed[i])
            {
                continue;
            }
            if (degree[i] == 1)
            {
                q.push(i);
                removed[i] = 1;
            }
        } // 这是第一层

        int qSize = q.size();
        for (int i = 0; i < qSize; i++)
        {
            int node = q.front();
            q.pop();
            for (auto neighbor : graph[node])
            {
                if (removed[neighbor])
                {
                    continue;
                }
                degree[neighbor]--;
                if (degree[neighbor] == 1)
                {
                    q.push(neighbor);
                    removed[neighbor] = 1;
                }
            }
        } // 这是第二层

        int nodeCount = 0;
        for (int i = 0; i < n; i++)
        {
            if (!removed[i])
            {
                nodeCount += 1;
            }
        }

        return max(0, 2 * nodeCount - 2);
    }
};